/*
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

*/

void swap(int index1, int index2, int *nums);

void sortColors(int* nums, int numsSize){
    int index1 = 0;   //slow index
    int index2 = 1;   //fast index

    int no_red = 0;     //记录未排序区域是否已经没有红色
    int no_white = 0;   //记录未排序区域是否已经没有白色

    while(index1 < numsSize)
    {
        if(nums[index1] == 0)
        {
            //do nothing
        }
        else if(nums[index1] == 1)
        {
            if(!no_red)
            {
                while(index2 < numsSize && nums[index2] != 0)
                {
                    index2++;
                }
                if(index2 < numsSize)
                {
                    swap(index1, index2, nums);
                }
                else
                {
                    //后面已经没有红色了
                    no_red = 1;
                }
            }
        }
        else
        {
            if(no_red)
            {
                if(!no_white)
                {
                    while(index2 < numsSize && nums[index2] != 1)
                    {
                        index2++;
                    }
                    if(index2 < numsSize)
                    {
                        swap(index1, index2, nums);
                    }
                    else
                    {
                        no_white = 1;
                    }
                }
            }
            else
            {
                int record_pos = index2;
                while(index2 < numsSize && nums[index2] != 0)
                {
                    index2++;
                }
                if(index2 < numsSize)
                {
                    swap(index1, index2, nums);
                }
                else
                {
                    no_red = 1;
                    index2 = record_pos;

                    if(!no_white)
                    {
                        while(index2 < numsSize && nums[index2] != 1)
                        {
                            index2++;
                        }
                        if(index2 < numsSize)
                        {
                            swap(index1, index2, nums);
                        }
                        else
                        {
                            no_white = 1;
                        }
                    }
                }
            }
        }

        index1++;
        index2 = index1 + 1;
        /*
        for(int i=0; i<numsSize; i++)
        {
            printf("%d ",nums[i]);
        }
        printf("\n");
        */
    }
}

void swap(int index1, int index2, int *nums)
{
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}